/*
 * @Description:
 * @Author: huangmin
 * @Email: 812949176@qq.com
 * @Date: 2023-02-24 09:22:05
 * @LastEditors: huangmin
 * @LastEditTime: 2023-03-10 14:00:28
 * @FilePath: /virtual-list/src/component/VirtualList/dp.js
 */
/**
 * @description: 选过的图片 高度置为Infinity
 * @param {*} arr
 * @param {*} omitIndexes
 * @return {*}
 */
const omitByIndexes = (arr, omitIndexes) => {
  omitIndexes.forEach((idx) => {
    arr[idx] = Infinity;
  });
  return arr;
};
/**
 * @description: 返回列高度差之和
 * @param {*} sortArr
 * @return {*}
 */
const calcTotalGap = (sortArr) => {
  return sortArr.reduce((pre, cur, index) => {
    if (0 < index) {
      return pre + sortArr[0] - cur;
    } else {
      return pre;
    }
  }, 0);
};
/**
 * @description: 动态规划算法 参考0-1背包问题 一维数组实现
 * @param {*} heights 高度数组
 * @param {*} bagVolume 背包体积
 * @return {*}
 */
const dp = (heights, bagVolume) => {
  let dpMatrix = [];
  // 基础状态 只考虑第一个图片的情况
  for (let cap = 0; cap <= bagVolume; cap++) {
    dpMatrix[cap] =
      heights[0] > cap
        ? { max: 0, indexes: [] }
        : { max: heights[0], indexes: [0] };
  }
  for (
    let useHeightIndex = 1;
    useHeightIndex < heights.length;
    useHeightIndex++
  ) {
    const currentHeight = heights[useHeightIndex];
    const currentHeightRound = Math.round(currentHeight);
    // 一维数组动态规划，需倒序遍历，当高度小于当前图片，则不可能考虑该张图片了
    for (let cap = bagVolume; cap >= currentHeightRound; cap--) {
      // 这里有个小坑 剩余高度一定要是整数，否则dp数组里取到的是undefined
      const useThisHeightRestCap = cap - currentHeightRound;
      const useThisHeightPrevDp = dpMatrix[useThisHeightRestCap];
      const useThisHeightMax = currentHeight + useThisHeightPrevDp.max;
      // 是否把当前图片纳入选择 如果取当前的图片大于不取当前图片的高度则更新
      // 大循环浮点数比较很消耗性能，这里选择四舍五入为整数比较会快20%，但也会造成一些误差
      if (Math.round(useThisHeightMax) > Math.round(dpMatrix[cap].max)) {
        dpMatrix[cap] = {
          max: useThisHeightMax,
          indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex),
        };
      }
    }
  }
  return dpMatrix[bagVolume];
};
/**
 * @description: 使用动态规划算法初始化瀑布流布局数据，仅能算出近似最优解。
 * @param {*} data
 * @param {*} listHeights
 * @return {*}
 */
const initWaterFallByDp = (data, listHeights) => {
  const listHeightsSort = [...listHeights].sort((a, b) => b - a);
  let bagCount = listHeightsSort.length;
  let dpData = data;
  let totalVolume = dpData.reduce((total, value) => {
    return total + value;
  }, 0);
  if (!totalVolume) {
    return;
  }
  const dpArr = Array(bagCount)
    .fill([])
    .map((item, index) => {
      if (1 < bagCount) {
        // 将列高度差也纳入运算，在动态规划时尽量抹平差距，需要排序对高度大的列先进行分配
        let bagVolume = Math.round(
          (totalVolume - calcTotalGap(listHeightsSort.slice(index))) / bagCount
        );
        bagVolume = bagVolume > 0 ? bagVolume : 0;
        const res = dp(dpData, bagVolume);
        item = res.indexes;
        // console.log({ max: res.max, indexes: item }, bagVolume, totalVolume);
        totalVolume -= res.max;
        bagCount--;
        dpData = omitByIndexes(dpData, item);
      } else {
        item = Array.from(dpData.keys()).filter(
          (key) => dpData[key] !== Infinity
        );
        // console.log({ max: totalVolume, indexes: item }, totalVolume);
      }
      return item;
    });

  return listHeights.map((item) => {
    const index = listHeightsSort.lastIndexOf(item);
    listHeightsSort[index] = -1;
    return dpArr[index];
  });
};

export default initWaterFallByDp;
